package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作： 
//
// 1. set(string key, string value, int timestamp) 
//
// 
// 存储键 key、值 value，以及给定的时间戳 timestamp。 
// 
//
// 2. get(string key, int timestamp) 
//
// 
// 返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp。 
//
// 如果有多个这样的值，则返回对应最大的 timestamp_prev 的那个值。 
// 如果没有值，则返回空字符串（""）。 
// 
//
// 
//
// 示例 1： 
//
// 输入：inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["f
//oo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
//输出：[null,null,"bar","bar",null,"bar2","bar2"]
//解释：  
//TimeMap kv;   
//kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1   
//kv.get("foo", 1);  // 输出 "bar"   
//kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即
// "bar"）   
//kv.set("foo", "bar2", 4);   
//kv.get("foo", 4); // 输出 "bar2"   
//kv.get("foo", 5); // 输出 "bar2"   
//
// 
//
// 示例 2： 
//
// 输入：inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [
//[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["lov
//e",20],["love",25]]
//输出：[null,null,null,"","high","high","low","low"]
// 
//
// 
//
// 提示： 
//
// 
// 所有的键/值字符串都是小写的。 
// 所有的键/值字符串长度都在 [1, 100] 范围内。 
// 所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。 
// 1 <= timestamp <= 10^7 
// TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。 
// 
// Related Topics 哈希表 二分查找 
// 👍 67 👎 0


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TimeBasedKeyValueStore{
    public static void main(String[] args) {
        TimeMap solution = new TimeBasedKeyValueStore().new TimeMap();
        solution.set("love","high",10);
        solution.set("love","low",20);
        System.out.println(solution.get("love",5));
        System.out.println(solution.get("love",10));
        System.out.println(solution.get("love",15));
        System.out.println(solution.get("love",20));
        System.out.println(solution.get("love",25));

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class TimeMap {

        private Map<String, List<Pair>> map;

        /**
         * Initialize your data structure here.
         */
        public TimeMap() {
            map = new HashMap<>();
        }

        public void set(String key, String value, int timestamp) {
            List<Pair> pairs = map.get(key);
            if (pairs == null) {
                pairs = new ArrayList<>();
                map.put(key, pairs);
            }
            pairs.add(new Pair(timestamp, value));
        }

        public String get(String key, int timestamp) {
            List<Pair> pairs = map.get(key);
            if (pairs == null || pairs.size() == 0) {
                return null;
            }

            int l = 0;
            int r = pairs.size() - 1;
            int m = -1;
            while (l + 1 < r) {
                m = (r - l) / 2 + l;
                int tmpTimestamp = pairs.get(m).getTimestamp();
                if (tmpTimestamp < timestamp) {
                    l = m;
                } else {
                    r = m;
                }
            }

            if (pairs.get(r).getTimestamp() <= timestamp) return pairs.get(r).getValue();
            else if (pairs.get(l).getTimestamp() <= timestamp) return pairs.get(l).getValue();
            return "";
        }

        class Pair{
            int timestamp;
            String value;

            public Pair(int timestamp, String value) {
                this.timestamp = timestamp;
                this.value = value;
            }

            public int getTimestamp() {
                return timestamp;
            }

            public void setTimestamp(int timestamp) {
                this.timestamp = timestamp;
            }

            public String getValue() {
                return value;
            }

            public void setValue(String value) {
                this.value = value;
            }
        }
    }

    /**
     * Your TimeMap object will be instantiated and called as such:
     * TimeMap obj = new TimeMap();
     * obj.set(key,value,timestamp);
     * String param_2 = obj.get(key,timestamp);
     */
    //leetcode submit region end(Prohibit modification and deletion)

}
